In networking systems, routers and/or switches typically move packets of information from one of a number of input ports to one or more output ports. In some applications, a packet may need to be duplicated on multiple output ports. A “unicast” type packet is intended for only one output port while a “multicast” type packet is intended for multiple output ports. Modern systems must be able to handle both of these packet types. Control of the sequence/flow of such packets for an output port can present a number of system design challenges and result in system limitations, as will be discussed in more detail below with reference to FIGS. 2-4.
Referring now to FIG. 1, a block diagram of a conventional router/switch system arrangement is shown and indicated by the general reference character 100. Input Ports 1, 2, . . . N can connect to Packet Receive 102, which can send Packet Headers to Lookup Engine 104 and Packets (Data and Headers) to Packet Storage Unit 108. The packet storage unit can store the packet data and the locations of this packet data can be identified by packet “pointers.” Typically, only one copy of the packet data may be stored in the packet storage unit regardless of the packet type (e.g., unicast or multicast). Lookup Engine 104 can provide signals 10 to Transmit Queue Control 106. Signals 110 can include a packet type indication (e.g., unicast or multicast), a transmit port number, and/or a packet pointer, for example. Further, the packet type information can also include a known Media Access Control Destination Address (MACDA) or an unknown MACDA, which may indicate a “flooding” operation is to be performed. Generally speaking, “flooding” means to transmit a packet to all output ports except the incoming port. Such a packet may still be considered a multicast type of packet. Flooding can ensure that a packet will reach its intended destination, even though its MACDA is not known. Transmit Queue Control 106 can provide signals 112 to Packet Storage Unit 108, which can store data and control the selections to Output Ports 1, 2, . . . N. Signals 112 can include information such as a transmit enable, a packet pointer, and/or a transmit port number. In other words, Transmit Queue Control 106 can “schedule” or set an order of the packets to be transmitted for each output port in the system by indicating the packet pointer in signals 112. Next, three different conventional approaches to providing this control function will be described, along with drawbacks of each.
Referring now to FIG. 2, a block diagram of a conventional single multicast queue system is shown and indicated by the general reference character 200. This system contains a separate pointer first-in first-out (FIFO) structure for multicast type packets. A Packet Pointer can be received by controller 202, which can determine, for example, if the packet is unicast or multicast type. If Unicast, the packet can be sent to one of Unicast Pointer FIFO 204-1, 204-2, . . . 204-N, which each corresponding to Port 1, Port 2, . . . Port N, respectively. If Multicast/Flooded (i.e., if the packet is multicast type or the MACDA is unknown), the packet can be sent to Multicast Pointer FIFO 206. An output of Multicast Pointer FIFO 206 can connect to each of de-queue controllers 208-1, 208-2, . . . 208-N, one for each output port. Disadvantages of this approach include misordering of unicast frames and head-of-line (HOL) blocking. The misordering results from unicast and multicast/flooding packets not being queued together and this can be especially problematic for Ethernet switches. The HOL flooding problem causes unnecessary starvation of uncongested output ports due to a few congested output ports.
Referring now to FIG. 3, a block diagram of a conventional “N” multicast queue system is shown and indicated by the general reference character 300. This system does not have a dedicated multicast queue, as each port has its own FIFO structure. A Packet Pointer can be received by controller 302 and passed to one of Pointer FIFO 304-1, 304-2, . . . 304-N for a Unicast determination (i.e., a unicast type packet). If Multicast/Flooded, each of the Pointer FIFOs that is a member of the associated multicast group receives the pointer. Disadvantages of this approach include a high memory bandwidth requirement and difficulty with queue re-sizing and/or excessive memory space requirements.
Referring now to FIG. 4, a block diagram of a conventional dispatch first-in first-out (FIFO) system is shown and indicated by the general reference character 400. A Packet Pointer can be received by controller 402 and then sent to either Dispatch FIFO 404 or to Packet Discard (if the dispatch FIFO is full). The pointer can be routed from Dispatch FIFO 404 to one or more of Pointer FIFO 406-1, 406-2, . . . 406-N, where each corresponds to a particular output port. Disadvantages of this approach include HOL blocking, unnecessary packet discard, and overall performance.
Consequently, what is needed is a transmit queue control solution with efficient pointer storage, prevention of multicast packets blocking unicast packets, line rate capable system performance, dynamic queue re-sizing, HOL blocking prevention, and strict packet ordering.